package cm.unit4.theme4;

import cm.commom.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5
 * 二叉树和双向链表
 */
public class ConvertDemo {

    // 前序
    public void preTravel(TreeNode treeNode, List<TreeNode> list) {
        if (treeNode != null) {
            if (treeNode.left != null) {
                preTravel(treeNode.left, list);
            }
            list.add(treeNode);
            if (treeNode.right != null) {
                preTravel(treeNode.right, list);
            }
        }
    }

    public TreeNode Convert01(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return null;
        }

        List<TreeNode> list = new ArrayList<>();
        preTravel(pRootOfTree, list);
        TreeNode head = list.get(0);
        head.left = null;
        if (list.size() <= 1) {
            head.right = null;
            return head;
        }

        head.right = list.get(1);
        TreeNode node = null;
        int i = 1;
        for (; i < list.size() - 1; i++) {
            node = list.get(i);
            node.left = list.get(i-1);
            node.right = list.get(i+1);
        }
        list.get(i).left = list.get(i-1);
        list.get(i).right = null;

        return head;
    }

    /**
     * 算法核心：中序遍历 + 指针记录当前链表最后结点
     */
    // pLast用于记录当前链表的末尾节点
    private TreeNode pLast = null;

    public TreeNode Convert(TreeNode root) {
        if (root == null)
            return null;

        // 递归处理左子树，左子树必然在链表前面
        TreeNode head = Convert(root.left);

        // 如果左子树为空，那么根节点root为双向链表的头节点
        if (head == null){
            head = root;
        }

        // root为（左右子树的）中间结点，连接当前节点root和当前链表的尾节点pLast
        root.left = pLast;
        if (pLast != null){
            pLast.right = root;
        }
        pLast = root;

        // 递归处理右子树，右子树必然在链表后面
        Convert(root.right);

        // 只用返回左子树
        return head;
    }
}
